// https://leetcode.cn/problems/insertion-sort-list/
// Created by ade on 2022/8/18.
// 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
//
// 插入排序 算法的步骤:
//
// 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
// 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
// 重复直到所有输入数据插入完为止。
// 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
//
// 对链表进行插入排序。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    // 升序 最笨的方法 用栈的方式
    ListNode *insertionSortList1(ListNode *head) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        vector < ListNode * > st = {};
        ListNode *index = head->next;
        while (index) {
            ListNode *tmp = dummy;
            while (tmp != index) {
                st.push_back(tmp);
                tmp = tmp->next;
            }

            ListNode *iNext = index->next;
            while (st.size() > 1) {
                auto back = st.back();
                if (index->val >= back->val) break;
                st.pop_back();

                ListNode *next = index->next;
                index->next = back;
                back->next = next;

                ListNode *backPrev = st.back();
                backPrev->next = index;
            }
            st.clear();
            index = iNext;
        }

        return dummy->next;
    }

    // 重点：cur永远是lastSorted的next元素
    ListNode *insertionSortList(ListNode *head) {
        if (!head || !head->next) return head;
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;

        ListNode *cur = head->next;
        ListNode *lastSorted = head;
        while (cur) {
            if (cur->val >= lastSorted->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode *prev = dummy;
                while (prev->next->val <= cur->val) {
                    prev = prev->next;
                }
                lastSorted->next = cur->next;
                cur->next = prev->next;
                prev->next = cur;
            }
            cur = lastSorted->next;
        }

        return dummy->next;
    }

    ListNode *init() {
        ListNode *head = new ListNode(4);
        ListNode *h1 = new ListNode(2);
        ListNode *h2 = new ListNode(1);
        ListNode *h3 = new ListNode(3);
        head->next = h1;
        h1->next = h2;
        h2->next = h3;
        return head;
    }

    void show(ListNode *head) {
        while (head) {
            cout << head->val << ",";
            head = head->next;
        }
        cout << endl;
    }
};

int main() {
    Solution so;
    ListNode *h = so.init();
    so.show(h);
    ListNode *h1 = so.insertionSortList(h);
    so.show(h1);
    return 0;
}